//题目:
// 一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。
// 在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。
// 给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。
// 示例 1：
// 输入： [1,2,3,1]
// 输出： 4
// 解释： 选择 1 号预约和 3 号预约，总时长 = 1 + 3 = 4。

// 示例 2：
// 输入： [2,7,9,3,1]
// 输出： 12
// 解释： 选择 1 号预约、 3 号预约和 5 号预约，总时长 = 2 + 9 + 1 = 12。

// 示例 3：
// 输入： [2,1,4,5,3,1,1,3]
// 输出： 12
// 解释： 选择 1 号预约、 3 号预约、 5 号预约和 8 号预约，总时长 = 2 + 4 + 3 + 3 = 12。
#include<iostream>
#include<vector>

using namespace std;
//代码
class Solution 
{
    int ret=0;
    vector<int> dp;//记录从第i个位置开始，到达最后一个位置的最大总预约时间
public:
    // void dfs(const vector<int>& nums,int pos,int sum)
    // {
    //     if(pos>=nums.size()){
    //         ret=max(ret,sum)
    //         return;
    //     }
    //     //寻找下一个落脚点
    //     dfs(nums,pos+2,nums[pos]+sum);
    //     dfs(nums,pos+3,nums[pos]+sum);
    // }

    int dfs(const vector<int>& nums,int pos)
    {
        if(pos>=nums.size()) return 0;

        if(dp[pos]!=0) return dp[pos];
        
        //寻找下一个落脚点
        int next_one=nums[pos]+dfs(nums,pos+2);
        int next_two=nums[pos]+dfs(nums,pos+3);

        dp[pos]=next_one>next_two?next_one:next_two;
        return dp[pos];
    }
    int massage(vector<int>& nums) 
    {
        if(nums.size()==0) return 0;
        //提议转换  给定一个数组，要求：从数组中选择一组数据，使得这组数据的和最大（选择的数据不能相邻）
        //法一：全排列————超时
        // dfs(nums,0,0);
        // dfs(nums,1,0);
        // return ret;

        //法二：优化————记忆化搜索————超时（全0）
        // dp.resize(nums.size(),0);
        // int ret1=dfs(nums,0);
        // int ret2=dfs(nums,1);
        // return ret1>ret2?ret1:ret2;

        // //法三：动态规划
        // //1.创建dp表————记录从初始位置，到第i个位置的最大总预约时间
        // vector<int> dp(nums.size());
        // //2.初始化
        // if(nums.size()==1) return nums[0];
        // dp[0]=nums[0],dp[1]=nums[1];
        // //3.填表————动态转移方程:dp[i]=nums[i]+max(dp[i-2],dp[i-3]);
        // for(int i=2;i<nums.size();i++)
        // {
        //     if(i-3<0)
        //         dp[i]=nums[i]+dp[i-2];
        //     else
        //         dp[i]=nums[i]+max(dp[i-2],dp[i-3]);
        // }
        // //4.确定返回值
        // int ret1=dp[nums.size()-1];
        // int ret2=dp[nums.size()-2];
        // return ret1>ret2?ret1:ret2;

        //法四：动态规划
        //1.创建dp细化表
        vector<int> f(nums.size());//记录从初始位置，到第i个位置时，选择第i个位置的最大总预约时间
        vector<int> g(nums.size());//记录从初始位置，到第i个位置时，不选第i个位置的最大总预约时间
        //2.初始化
        if(nums.size()==1) return nums[0];
        f[0]=nums[0],g[0]=0;
        //3.填表————动态转移方程:f[i]=nums[i]+g[i-1]  g[i]=max(f[i-1],g[i-1]);
        for(int i=1;i<nums.size();i++)
        {
            f[i]=nums[i]+g[i-1];  
            g[i]=max(f[i-1],g[i-1]);
        }
        //4.确定返回值
        int ret1=f[nums.size()-1];
        int ret2=g[nums.size()-1];
        return ret1>ret2?ret1:ret2;
    }
};